import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Test {

    /*
    二叉树的最近公共祖先
     */
    //递归求法
    //如果左右两边分别找到p 和 q，那么返回 root
    //但如果只有一边找到了p 或 q ，那么返回 p 或 q 所在节点！
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor1(root.left,p,q);
        TreeNode right = lowestCommonAncestor1((root.right,p,q));
        if(left != null && right != null){
            return root;
        }else if(left != null){
            return left;
        }else if(right != null){
            return right;
        }else{
            return null;
        }
    }
    //方法二——路径方法
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        int size = size1 - size2;
        if(size > 0){
            while(size > 0){
                stack1.pop();
                size--;
            }
        }else{
            size = -size;
            while(size > 0){
                stack2.pop();
                size--;
            }
        }
        while(!stack1.isEmpty()){
            if(stack1.peek() != stack2.peek()){
                stack1.pop();
                stack2.pop();
            }else{
                return stack1.pop();
            }
        }
        return null;
    }
    private boolean getPath(TreeNode root,TreeNode key,Deque<TreeNode> stack){
        if(root == null){
            return false;
        }
        stack.push(root);
        if(root.val == key.val){
            return true;
        }
        boolean left = getPath(root.left,key,stack);
        if(left == true){
            return true;
        }
        boolean right = getPath(root.right,key,stack);
        if(right == true){
            return true;
        }
        stack.pop();
        return false;
    }

    /*
    题目 2 : 二叉搜索树的最近公共祖先
     */
    //自己的思路：
    public TreeNode  lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(p.val >= root.val && q.val <= root.val || q.val >= root.val && p.val <= root.val){
            return root;
        }
        if(p.val < root.val && q.val < root.val){
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            if(left != null){
                return left;
            }
        }
        if(p.val > root.val && q.val > root.val){
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(right != null){
                return right;
            }
        }
        return null;
    }
    //官方写法，不用递归了，直接迭代
    public TreeNode  lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while(true){
            if(p.val < ancestor.val && q.val < ancestor.val){
                ancestor = ancestor.left;
            }else if(p.val > ancestor.val && q.val > ancestor.val){
                ancestor = ancestor.right;
            }else{
                break;
            }
        }
        return ancestor;
    }
}
